package com.ctgu.蓝桥杯真题.B组2016;

import java.util.ArrayList;
import java.util.Arrays;

/**
 * @author: Backdiy
 * @data: 2021/4/14 21:15
 * @desc:
 */
public class F方格填数 {
    public static void main(String[] args) {
        全排列.main();
        深搜.main();
    }
//利用全排列然后去除不符合条件的情况
    static class 全排列 {
        static int[] num = new int[]{1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
        static int ans = 0;

        public static void main() {
            dfs(0, 9);
            System.out.println(ans);
        }

        static void swap(int i, int j) {
            int t = num[i];
            num[i] = num[j];
            num[j] = t;
        }

        static void dfs(int k, int n) {
            if (k == n) {
                if (check()) {
                    ans++;
                }
            } else {
                for (int i = k; i <= n; i++) {
                    swap(i, k);
                    dfs(k + 1, n);
                    swap(i, k);
                }
            }
        }

        static boolean check() {
            ArrayList<Integer> integers = new ArrayList<>();
            integers.add(num[0] - num[1]);
            integers.add(num[0] - num[3]);
            integers.add(num[0] - num[4]);
            integers.add(num[0] - num[5]);
            integers.add(num[1] - num[2]);
            integers.add(num[1] - num[4]);
            integers.add(num[1] - num[5]);
            integers.add(num[1] - num[6]);
            integers.add(num[2] - num[5]);
            integers.add(num[2] - num[6]);
            integers.add(num[3] - num[4]);
            integers.add(num[3] - num[7]);
            integers.add(num[3] - num[8]);
            integers.add(num[4] - num[5]);
            integers.add(num[4] - num[7]);
            integers.add(num[4] - num[8]);
            integers.add(num[4] - num[9]);
            integers.add(num[5] - num[9]);
            integers.add(num[5] - num[6]);
            integers.add(num[5] - num[8]);
            integers.add(num[6] - num[9]);
            integers.add(num[7] - num[8]);
            integers.add(num[8] - num[9]);
            for (Integer i :
                    integers) {
                if (Math.abs(i) == 1) {
                    return false;
                }
            }
            return true;
        }
    }
//八皇后问题，递归出每一种情况，判断是否能放入这个数
    static class 深搜 {
        static int[][] num = new int[5][6];
        static int[] vis = new int[10];
        static int ans = 0;

        public static void main() {
            for (int i = 0; i < 5; i++) {
                for (int j = 0; j < 6; j++) {
                    num[i][j] = -10;
                }
            }
            dfs(1, 2);
            System.out.println(ans);
        }

        static void dfs(int x, int y) {
            if (x == 3 && y == 4) {
                ans++;
                return;
            }
            for (int i = 0; i < 10; i++) {
                if (vis[i] == 0) {
                    num[x][y] = i;
                    if (!check(x, y)) {
                        num[x][y] = -10;
                        continue;
                    }
                    vis[i] = 1;
                    if (y == 4) {
                        dfs(x + 1, 1);
                    } else {
                        dfs(x, y + 1);
                    }
                    vis[i] = 0;
                    num[x][y] = -10;
                }
            }

        }

        static boolean check(int x, int y) {
            for (int i = x - 1; i <= x + 1; i++) {
                for (int j = y - 1; j <= y + 1; j++) {
                    if (Math.abs(num[x][y] - num[i][j]) == 1) {
                        return false;
                    }
                }
            }
            return true;
        }
    }
}
